package com.aikon.wht.paoshan.alg;

/**
 * 字符串匹配
 *
 * 单模串
 * 1.bf算法
 *      暴力匹配算法 主串n个字符 模串m个字符 最坏情况下暴力匹配需要比对(n-m+1)*m次，时间复杂度O(n*m)
 *      实际开发中常用，实际开发中字符数有限，且实现简单，符合kiss(keep it simple and stupid)原则
 * 2.rk算法
 *      bf算法的进阶版 对所有n-m+1个子串做哈希，与模串的哈希匹配，时间复杂度O(n)。其核心在于优化子串的哈希方式。
 *      例如主串a = 1234567890 模串b = 678，则有子串s[] = {123,234,345,456,567,678,789,890}，对子串做m进制(m=b.length=3)计算得到：
 *      h[] = {1*9+2*3+3,2*9+3*3+4,3*9+4*3+5,4*9+5*3+6,5*9+6*3+7,6*9+7*3+8,7*9+8*3+9,8*9+9*3+0}，由于相邻子串必有两位相同，
 *      故有 h[i]=(h[i-1]-a[i-1]*m^(m-1))*m+a[i+m-1] (i>0)
 *      如果有哈希冲突，需要比对子串与模串的字符。极端情况下会退化为O(n*m)。
 * 3.bm算法
 *      在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。
 *      坏字符法则 - 从模串末尾倒着往前匹配，当发现某字符不匹配是，这个主串中不匹配的字符为坏字符。坏字符对应的模串中的字符下标记作si，
 *                   如果坏字符在模串中存在，模串中对应位置下标记作xi，如果不存在xi记作-1。那模串向后移动si-xi继续匹配。
 *      好后缀法则 - 从模串末尾倒着往前匹配，如果有匹配的模串后缀，即为好后缀，其前一个字符即为坏字符。拿好后缀在模串中查找，
 *                   如果有匹配的，则模串后移到对齐的位置。如果没有匹配的，且模串前缀与好后缀部分重合，则模串向后移动到部分重合的地方，
 *                   否则移动到好后缀后面。
 * 4.kmp算法
 *
 *
 * 多模串
 * trie树
 * ac自动机
 *
 * @author WANGHAITAO273
 */
public class PaoshanOfString {


}
